{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "29539fb6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nLinked List链表 与 list列表\\n\\n链表按排序规律分：\\n    unorderedlist无序链表\\n    orderedlist有序链表【按某种规律排序的链表】   \\n按链接方式分：\\n    单链表\\n    双链表【前后节点互相指】\\n\\n\\n链表们的优点\\n1.插入，删除数据都很快\\n2.可以在任何位置对数据进行增，删，改\\n\\n链表们的缺点\\n1.查询满【随机访问慢】\\n'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Linked List链表 与 list列表\n",
    "\n",
    "链表按排序规律分：\n",
    "    unorderedlist无序链表\n",
    "    orderedlist有序链表【按某种规律排序的链表】   \n",
    "按链接方式分：\n",
    "    单链表\n",
    "    双链表【前后节点互相指】\n",
    "    循环链表【单链表的t=0节点不再是None，而是最新的节点，从而构成环】\n",
    "\n",
    "链表们的优点\n",
    "1.插入，删除数据都很快\n",
    "2.可以在任何位置对数据进行增，删，改\n",
    "3.不需要连续的地址空间,不容易产生内存碎片\n",
    "4.不需要扩容\n",
    "\n",
    "链表们的缺点\n",
    "1.查询满【随机访问慢】\n",
    "\n",
    "\n",
    "链表的意义：\n",
    "1.LinkedList 适用于频繁插入与删除的场景,并且,不存在扩容的问题,但是,并不擅长随机访问,由于内存的不连续性,不存在内存碎片的问题,\n",
    "  同时,可以当成是队列和栈来使用\n",
    "2.链表可以用来表示图的邻接表\n",
    "\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a3021d47",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1.Node节点\n",
    "\n",
    "class Node():\n",
    "    def __init__(self,initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "     \n",
    "    def getNext(self):     # getnext是获得当前节点（t时进入的节点）之前的节点（t-1节点）\n",
    "        return self.next\n",
    "    def setData(self,newdata):\n",
    "        self.data = newdata\n",
    "    def setNext(self,newnext):\n",
    "        self.next = newnext\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c8b0fa56",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2.UnorderedList 无序链表\n",
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "    def add(self,item):\n",
    "        temp = Node(item)   # 实例化节点为temp\n",
    "        temp.setNext(self.head) # 将节点temp的下一个节点设置为self.head 【第一次self.head为None】\n",
    "        self.head = temp        # 将self.head更改为实例temp1，当我们再add时，实例temp2的setnext就会指向temp1\n",
    "                                # temp2——》temp1——》None\n",
    "    def length(self):\n",
    "        current = self.head            # self.head 在add一次后就由None变为了对象类型 self.head永远指向最新添加的节点\n",
    "        count = 0\n",
    "        while current != None:         # 遍历链表\n",
    "            count = count + 1\n",
    "            current = currente.getNext()    # 节点=上节点\n",
    "        return count\n",
    "    \n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "        return found\n",
    "    \n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        if previous == None:\n",
    "            self.head = current.getNext()  # 当被删数据t=1时，进行假删除，只是把指针放在了t=2的节点 \n",
    "        else:\n",
    "            previous.setNext(current.getNext()) # 当被删数据t=T时，进行假删除， 将t=T+1的next指向t=T-1，从而达到忽略被删除节点\n",
    "            current.setNext(None)               # 自己加的；这样被删节点就完全独立与链表了\n",
    "        return found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a21ddf44",
   "metadata": {},
   "outputs": [],
   "source": [
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "    \n",
    "    def length(self):\n",
    "        current = self.head            # self.head 在add一次后就由None变为了对象类型 self.head永远指向最新添加的节点\n",
    "        count = 0\n",
    "        while current != None:         # 遍历链表\n",
    "            count = count + 1\n",
    "            current = currente.getNext()    # 节点=上节点\n",
    "        return count\n",
    "    \n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        if previous == None:\n",
    "            self.head = current.getNext()  # 当被删数据t=1时，进行假删除，只是把指针放在了t=2的节点 \n",
    "        else:\n",
    "            previous.setNext(current.getNext()) # 当被删数据t=T时，进行假删除， 将t=T+1的next指向t=T-1，从而达到忽略被删除节点\n",
    "            current.setNext(None)               # 自己加的；这样被删节点就完全独立与链表了\n",
    "        return found\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        stop = False\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData()>item:\n",
    "                    stop = True\n",
    "                else:\n",
    "                    current = current.getNext()\n",
    "        return found\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f84ecca9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
